package com.arron.algorithm.leetcodetop100.双指针;

public class 接雨水 {


    /**
     * 双指针升级
     *  时间复杂度 O(n), 空间复杂度 O(1)
     * @param height
     * @return
     */
    public int trap_plus(int[] height) {
        int left = 0;
        int right = height.length-1;

        int l_max= 0;
        int r_max= 0;

        int res = 0;

        while (left < right) {

            l_max = Math.max(l_max, height[left]);
            r_max = Math.max(r_max, height[right]);

            if (l_max < r_max) {

                res += l_max - height[left];

                left++;
            } else {
                res += r_max - height[right];
                right--;
            }
        }

        return res;
    }














    /**
     * 时间复杂度 O（3N） == O(n) 空间复杂度 O(2n) = O(n)
     * 暴力破解法+记忆存储
     * @param height
     * @return
     */
    public int trap(int[] height) {


        //思路：考虑每个下标对应能够接的雨水有多少

        if (height.length<3){
            return 0;
        }

        //找到左边最高的柱子
        int[] l_max_nums = new int[height.length];
        //找到右边最高的柱子
        int[] r_max_nums = new int[height.length];
        l_max_nums[0] = height[0];
        //[0,1,0,2,1,0,1,3,2,1,2,1]
        //
        for (int j = 1; j<height.length ; j++) {
            l_max_nums[j] = Math.max(l_max_nums[j-1],height[j]);
        }
        r_max_nums[height.length-1] = height[height.length-1];
        for (int j = height.length-2; j >= 0 ; j--) {
            r_max_nums[j] = Math.max(r_max_nums[j+1],height[j]);
        }
        int res = 0;
        for (int i = 1; i < height.length-1; i++) {

           res += Math.min(l_max_nums[i],r_max_nums[i]) - height[i];
        }
        return res;
    }


    public static void main(String[] args) {
        接雨水 max = new 接雨水();
        int[] a = {0,1,0,2,1,0,1,3,2,1,2,1};
        max.trap(a);
    }

}
